Division, reciprocal, and square-root arithmetic operations decisively impact the performance of a data processing algorithm. These operations are usually performed using iterative algorithms such as the SRT (Sweeney, Robertson, and Tocher) algorithm, where result digits are computed sequentially using a given radix r (usually a power of 2). The result is computed iteratively, then eventually corrected, then eventually negated. The latter operations cannot be short-cut, since the need of a correction is detected in the last iteration of the computation. Accumulation of digits with MSD (Most Significant Digit) first to produce a final result usually produces carry information and requires the propagation of carries from one digit to the previous one.
Known solutions are to compute an intermediate result Q, and then run one more iteration to correct and/or negate. Another solution is to compute two intermediate results Q and Q−1, and then run one more iteration to negate eventually. The drawback of these solutions is that they include a supplementary iteration to correct and/or invert the final result. This supplementary iteration is described, for example, in U.S. Pat. No. 6,109,777.
EP 1,672,481 B1 describes an invention that relates to a division and square root arithmetic unit including a divider of a higher radix type and a square root extractor of a lower radix type. This patent describes how in designing a divider and a square root extractor, a device using a subtraction shift method or a subtraction separation method is generally employed to achieve a balance between performance and an amount of hardware required for implementation. This algorithm carries out a division by shifting a remainder or partial remainder and subtracting a multiple of a denominator (a divisor or a partially extracted square root) from the remainder to determine a quotient in a similar manner to a manual division calculation performed on paper. More specifically, a quotient or a number extracted from a square root is determined every n digits to calculate a partial remainder on the basis of the determined quotient or the extracted number from the square root. In the next operation step, the obtained partial remainder is shifted n digits to determine the next n-digit quotient or the square root extraction number on the basis of the n-digit shift of the partial remainder. Similarly, the operation is repeatedly performed.
A division and square root extraction processing of such algorithms is described, for example, in Kai Hwang, “High Speed Arithmetic System of Computers”, 1980, Kindai Kagaku Sha Co., Ltd., pp. 214-249. This document discloses various division methods such as a restoring division, a non-restoring division, an SRT division and a generalized SRT division.